Nonhomogeneous place-dependent Markov chains, unsynchronised AIMD, and optimisation

Title: Nonhomogeneous place-dependent Markov chains, unsynchronised AIMD, and optimisation
Creator: Wirth, Fabian R.; Stüdl, Sonja; Yu, Jia Yuan; Corless, Martin; Shorten, Robert
Relation: Journal of the ACM Vol. 66, Issue 4, no. 24
Publisher Link: http://dx.doi.org/10.1145/3312741
Publisher: Association for Computing Machinery
Resource Type: journal article
Date: 2019
Description: A stochastic algorithm is presented for a class of optimisation problems that arise when a group of agents compete to share a single constrained resource in an optimal manner. The approach uses intermittent single-bit feedback, which indicates a constraint violation and does not require inter-agent communication. The algorithm is based on a positive matrix model of AIMD, which is extended to the nonhomogeneous Markovian case. The key feature is the assignment of back-off probabilities to the individual agents as a function of the past average access to the resource. This leads to a nonhomogeneous Markov chain in an extended state space, and we show almost sure convergence of the average access to the social optimum.
Subject: nonhomogeneous place-dependent Markov chains; AIMD; invariant measure; iterated function systems; almost sure convergence; optimisation
Identifier: http://hdl.handle.net/1959.13/1463104
Identifier: uon:46639
Identifier: ISSN:0004-5411
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format